The present invention relates to the field of editing compressed images. More specifically, in one embodiment the invention provides means for editing portions of compressed images without decompressing the entire image.
Modern color imagery for cameras and scanners require huge amounts of memory to store image files containing a data representation of the input or scanned image. A typical image such as that used with a color copier with 8.5".times.11" (216 mm.times.297 mm) paper, a resolution of 400 dots per inch (15.75 per mm), and 3 bytes (24 bits) to represent the intensity of each dot, would occupy 44.88 megabytes of memory. In addition to the size of the memory, the memory must have high bandwidth for real time applications, such as a color copier where 15 pages per minute is a typical demand. This implies a bandwidth, or data rate, of 11.22 megabytes/second. Both these requirements drive up the cost of imaging systems. Compression techniques have been used to solve both the bandwidth and the storage problems for quite a while. With compression, an image file can be stored in less memory, and moves faster across any bandwidth limited channel because of the lower number of bits used to represent an image. Compression involves passing the raw image data into a compressor, which combines and analyzes the patterns in the raw data to produce a compressed image file where the original image is not readily discernable without a corresponding decompression.
If an image is to be edited, scaled, rotated, or otherwise processed, random access to any or all of the pixels is required. Once the processing is complete, the edits must be saved to the image file. If the image file being processed is compressed, the conventional means for obtaining random pixel access is to decompress the image into a frame store, perform the processing, and then recompress the image into a new image file. The problem with this is that no memory is saved by decompressing, since memory is needed for the frame store. The bandwidth is also lowered, since compression and decompression of entire images takes time. This additional processing time and memory is often wasted, since even the most expensive display in an imaging system could not display the entire image a full resolution.
One solution is to allow only limited in-line real-time manipulation, manipulating the image as it moves through a channel from one compressed image to another. Unfortunately, only a small area can be processed at once, and such a scheme cannot be adapted to interactive editing.
Compression methods for compressing image data are known. One such compression standard is JPEG (Joint Photographic Experts Group). Other standards include JBIG, Fax G3 or G4, and GIF. In JPEG, to give one example, an image is represented by a two-dimensional array of picture elements, or pixels. If the image is grayscale, each pixel is represented by an intensity value, and if the image is color, each pixel is represented by several values. Before compressing the image data, the image is divided into blocks of eight by eight pixels each. Within each block, the 64 pixels are transformed, using a discrete cosine transform, into 64 frequency amplitudes, a DC value and 63 AC values. Rather than encoding the DC value directly, the DC value of the block preceding the current block is subtracted from the DC value of the current block, and the resulting differential DC value is stored. Because the typical image being compressed has a constant color within each eight by eight pixel block and a relatively slowly changing average color value, this scheme results in greatly compressed images. Many other image compression schemes use similar techniques for compression and the use of differential values.
An image comprises raw pixel data indicating color or intensity at a number of pixel locations, usually a two-dimensional grid. Pixels are grouped into blocks, and each block is compressed separately. The process of compression involves transforming the 64 values associated with the block into one differential DC value and 63 AC values, and reducing the number of bits needed to describe the transformed values through entropy encoding. Each block is compressed into a minimum coded unit (MCU), the MCUs which make up a compressed image are tagged with identifying information, such as the block location within the image, length data to indicate how many bits are contained in the MCU, and the like, and the MCUs are stored sequentially in an image file. Length data is needed since MCUs vary in length. The length is determined by the entropy encoding step. A block which is very ordered, such as a uniformly colored block will compress into a relatively small MCU as compared to a block with more color variation. The process of entropy encoding is generally referred to as coding, whereas a compressing process involves blocking, cosine transforming and coding image data. Significantly, differential DC values can be read from an MCU which has been decoded only, since full decompression is not necessary. This savings in processing resources may be significant since cosine transforms and inverse transforms can be very computationally intensive operations.
To decompress an image, each MCU from an image file is decompressed into a block, by reverse operation of the differential encoding of the DC value and by an inverse cosine transform. While differential encoding of slowly changing values from block to block increases the compression, it increases the difficulty of decompressing only a part of an image, since decompression of some MCUs in the partial image will require reference to MCUs which are not in the partial image. Further difficulties arise in partial decompression when the partial image is edited and recompressed. Because the degree of compression depends on the image data, an edited partial image will usually be a different size when compressed compared with the original image. Consequently, simply replacing the MCUs from the partial image with the MCUs from the edited partial image is impractical, unless the entire image is decompressed, edited and recompressed. From the above it is seen that an improved method for manipulating and editing compressed images is needed.